/********************************************************
 * Kernels to be optimized for the CS:APP Performance Lab
 ********************************************************/

#include <stdio.h>
#include <stdlib.h>
#include "defs.h"

/* The size of a block. */
const int BLOCK_SIZE = 32;

/* 
 * Please fill in the following team struct 
 */
team_t team = {
    "tguh3+thsu4",              /* Team name */

    "Ten-Young Guh",     /* First member full name */
    "tguh3@binghamton.edu",  /* First member email address */

    "Thomas Hsu",  /* Second member full name (leave blank if none) */
    "thsu4@binghamton.edu"   /* Second member email addr (leave blank if none) */
};

/***************
 * ROTATE KERNEL
 ***************/

/******************************************************
 * Your different versions of the rotate kernel go here
 ******************************************************/

/* 
 * naive_rotate - The naive baseline version of rotate 
 */
char naive_rotate_descr[] = "naive_rotate: Naive baseline implementation";
void naive_rotate(int dim, pixel *src, pixel *dst) 
{
    int i, j;

    for (i = 0; i < dim; i++)
	for (j = 0; j < dim; j++)
	    dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];
}

/* 
 * rotate_swap_indices - Simply switches i and j for a little improvement
 */
char rotate_swap_indices_descr[] = "rotate_swap_indices: Switches i and j";
void rotate_swap_indices(int dim, pixel *src, pixel *dst)
{
    int i, j;

    for (j = 0; j < dim; j++)
	for (i = 0; i < dim; i++)
	    dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];
}

/* 
 * rotate_block - Also uses blocks
 */
char rotate_block_descr[] = "rotate_block: Uses 32x32 blocks";
void rotate_block(int dim, pixel *src, pixel *dst)
{
    int i, j;
    int ii; int jj;

    for (j = 0; j < dim; j += BLOCK_SIZE)
	for (i = 0; i < dim; i += BLOCK_SIZE)
	  for (jj = 0; jj < BLOCK_SIZE; jj++)
	    for (ii = 0; ii < BLOCK_SIZE; ii++)
	      dst[RIDX(dim-1-j-jj, i+ii, dim)] = src[RIDX(i+ii, j+jj, dim)];
}

/* 
 * rotate_micro - Uses microoptimizations
 */
char rotate_micro_descr[] = "rotate_micro: Micro-optimized";
void rotate_micro(const int dim, pixel *const src, pixel *const dst)
{
    int i, j;
    int ii; int jj;
    const int dim_minus_1 = dim - 1;

    for (j = 0; j < dim; j += BLOCK_SIZE)
	for (i = 0; i < dim; i += BLOCK_SIZE)
	  for (jj = 0; jj < BLOCK_SIZE; jj++)
	    for (ii = 0; ii < BLOCK_SIZE; ii++)
	      {
		const int totalI = i + ii;
		const int totalJ = j + jj;
		dst[RIDX(dim_minus_1 - totalJ, totalI, dim)] = src[RIDX(totalI, totalJ, dim)];
	      }
}

/* 
 * rotate - Your current working version of rotate
 * IMPORTANT: This is the version you will be graded on
 */
char rotate_descr[] = "rotate: Current working version";
void rotate(int dim, pixel *src, pixel *dst) 
{
  rotate_micro(dim, src, dst);
}


/*********************************************************************
 * register_rotate_functions - Register all of your different versions
 *     of the rotate kernel with the driver by calling the
 *     add_rotate_function() for each test function. When you run the
 *     driver program, it will test and report the performance of each
 *     registered test function.  
 *********************************************************************/

void register_rotate_functions() 
{
    add_rotate_function(&naive_rotate, naive_rotate_descr);   
    add_rotate_function(&rotate, rotate_descr);   
    add_rotate_function(&rotate_swap_indices, rotate_swap_indices_descr);
    add_rotate_function(&rotate_block, rotate_block_descr);
    add_rotate_function(&rotate_micro, rotate_micro_descr);
    /* ... Register additional test functions here */
}


/***************
 * SMOOTH KERNEL
 **************/

/***************************************************************
 * Various typedefs and helper functions for the smooth function
 * You may modify these any way you like.
 **************************************************************/

/* A struct used to compute averaged pixel value */
typedef struct {
    int red;
    int green;
    int blue;
    int num;
} pixel_sum;

/* Compute min and max of two integers, respectively */
static int min(int a, int b) { return (a < b ? a : b); }
static int max(int a, int b) { return (a > b ? a : b); }

/* 
 * initialize_pixel_sum - Initializes all fields of sum to 0 
 */
static void initialize_pixel_sum(pixel_sum *sum) 
{
    sum->red = sum->green = sum->blue = 0;
    sum->num = 0;
    return;
}

/* 
 * accumulate_sum - Accumulates field values of p in corresponding 
 * fields of sum 
 */
static void accumulate_sum(pixel_sum *sum, pixel p) 
{
    sum->red += (int) p.red;
    sum->green += (int) p.green;
    sum->blue += (int) p.blue;
    sum->num++;
    return;
}

/* 
 * assign_sum_to_pixel - Computes averaged pixel value in current_pixel 
 */
static void assign_sum_to_pixel(pixel *current_pixel, pixel_sum sum) 
{
    current_pixel->red = (unsigned short) (sum.red/sum.num);
    current_pixel->green = (unsigned short) (sum.green/sum.num);
    current_pixel->blue = (unsigned short) (sum.blue/sum.num);
    return;
}

/* 
 * avg - Returns averaged pixel value at (i,j) 
 */
static pixel avg(int dim, int i, int j, pixel *src) 
{
    int ii, jj;
    pixel_sum sum;
    pixel current_pixel;

    initialize_pixel_sum(&sum);
    for(ii = max(i-1, 0); ii <= min(i+1, dim-1); ii++) 
      for(jj = max(j-1, 0); jj <= min(j+1, dim-1); jj++) 
	    accumulate_sum(&sum, src[RIDX(ii, jj, dim)]);

    assign_sum_to_pixel(&current_pixel, sum);
    return current_pixel;
}

/* 
 * avg_micro - Returns averaged pixel value at (i,j) 
 */
static pixel avg_micro(int dim, int i, int j, pixel *src) 
{
  const int lastii = min(i+1, dim-1);
  const int lastjj = min(j+1, dim-1);
    int ii, jj;
    pixel_sum sum;
    pixel current_pixel;

    initialize_pixel_sum(&sum);
    for(ii = max(i-1, 0); ii <= lastii; ii++) 
      for(jj = max(j-1, 0); jj <= lastjj; jj++) 
	    accumulate_sum(&sum, src[RIDX(ii, jj, dim)]);

    assign_sum_to_pixel(&current_pixel, sum);
    return current_pixel;
}


static pixel avg_unroll(int dim, int i, int j, pixel *src)
{
#define RED_CORNER_SUM(a, b, c, d) ((int)src[(a)].red + src[(b)].red + src[(c)].red + src[(d)].red)
#define GREEN_CORNER_SUM(a, b, c, d) ((int)src[(a)].green + src[(b)].green + src[(c)].green + src[(d)].green)
#define BLUE_CORNER_SUM(a, b, c, d) ((int)src[(a)].blue + src[(b)].blue + src[(c)].blue + src[(d)].blue)
#define COMP_CORNER_AVERAGE(s) ((unsigned short)((s)/4))
#define RED_EDGE_SUM(a, b, c, d, e, f) ((int)src[(a)].red + src[(b)].red + src[(c)].red + src[(d)].red + src[(e)].red + src[(f)].red)
#define GREEN_EDGE_SUM(a, b, c, d, e, f) ((int)src[(a)].green + src[(b)].green + src[(c)].green + src[(d)].green + src[(e)].green + src[(f)].green)
#define BLUE_EDGE_SUM(a, b, c, d, e, f) ((int)src[(a)].blue + src[(b)].blue + src[(c)].blue + src[(d)].blue + src[(e)].blue + src[(f)].blue)
#define COMP_EDGE_AVERAGE(sum) ((unsigned short)((sum)/6))

  pixel p;
  int a, b, c, d, e, f, g, h, ii;
  if (i == 0)
    {
      if (j == 0)
	{
	  d = dim + 1;

	  p.red = COMP_CORNER_AVERAGE(RED_CORNER_SUM(0, 1, dim, d));
	  p.green = COMP_CORNER_AVERAGE(GREEN_CORNER_SUM(0, 1, dim, d));
	  p.blue = COMP_CORNER_AVERAGE(BLUE_CORNER_SUM(0, 1, dim, d));
	}
      else if (j == dim - 1)
	{
	  a = j - 1;
	  c = a + dim;
	  d = j + dim;

	  p.red = COMP_CORNER_AVERAGE(RED_CORNER_SUM(a, j, c, d));
	  p.green = COMP_CORNER_AVERAGE(GREEN_CORNER_SUM(a, j, c, d));
	  p.blue = COMP_CORNER_AVERAGE(BLUE_CORNER_SUM(a, j, c, d));
	}
      else
	{
	  a = j - 1;
	  c = j + 1;
	  d = a + dim;
	  e = j + dim;
	  f = c + dim;

	  p.red = COMP_EDGE_AVERAGE(RED_EDGE_SUM((a),(j),(c),(d),(e),(f)));
	  p.green = COMP_EDGE_AVERAGE(GREEN_EDGE_SUM((a),(j),(c),(d),(e),(f)));
	  p.blue = COMP_EDGE_AVERAGE(BLUE_EDGE_SUM((a),(j),(c),(d),(e),(f)));
	}
    }
  else if (i == dim - 1)
    {
      if (j == 0)
	{
	  c = i * dim;
	  a = c - dim;
	  b = a + 1;
	  d = c + 1;

	  p.red = COMP_CORNER_AVERAGE(RED_CORNER_SUM(a, b, c, d));
	  p.green = COMP_CORNER_AVERAGE(GREEN_CORNER_SUM(a, b, c, d));
	  p.blue = COMP_CORNER_AVERAGE(BLUE_CORNER_SUM(a, b, c, d));
	}
      else if (j == dim - 1)
	{
	  c = j * dim + dim - 2;
	  a = c - dim;
	  b = a + 1;
	  d = c + 1;

	  p.red = COMP_CORNER_AVERAGE(RED_CORNER_SUM(a, b, c, d));
	  p.green = COMP_CORNER_AVERAGE(GREEN_CORNER_SUM(a, b, c, d));
	  p.blue = COMP_CORNER_AVERAGE(BLUE_CORNER_SUM(a, b, c, d));
	}
      else
	{
	  e = j + i * dim;
	  d = e - 1;
	  f = e + 1;
	  a = d - dim;
	  b = e - dim;
	  c = f - dim;

	  p.red = COMP_EDGE_AVERAGE(RED_EDGE_SUM((a),(b),(c),(d),(e),(f)));
	  p.green = COMP_EDGE_AVERAGE(GREEN_EDGE_SUM((a),(b),(c),(d),(e),(f)));
	  p.blue = COMP_EDGE_AVERAGE(BLUE_EDGE_SUM((a),(b),(c),(d),(e),(f)));
	}
    }
  else if (j == 0)
    {
      b = i * dim;
      a = b - dim;
      c = b + dim;
      d = a + 1;
      e = b + 1;
      f = c + 1;

      p.red = COMP_EDGE_AVERAGE(RED_EDGE_SUM((a),(b),(c),(d),(e),(f)));
      p.green = COMP_EDGE_AVERAGE(GREEN_EDGE_SUM((a),(b),(c),(d),(e),(f)));
      p.blue = COMP_EDGE_AVERAGE(BLUE_EDGE_SUM((a),(b),(c),(d),(e),(f)));

    }
  else if (j == dim - 1)
    {
      e = i * dim + j;
      d = e - dim;
      f = e + dim;
      a = d - 1;
      b = e - 1;
      c = f - 1;

      p.red = COMP_EDGE_AVERAGE(RED_EDGE_SUM((a),(b),(c),(d),(e),(f)));
      p.green = COMP_EDGE_AVERAGE(GREEN_EDGE_SUM((a),(b),(c),(d),(e),(f)));
      p.blue = COMP_EDGE_AVERAGE(BLUE_EDGE_SUM((a),(b),(c),(d),(e),(f)));
    }
  else
    {
      e = i * dim + j;
      d = e - 1;
      f = e + 1;

      b = e - dim;
      a = b - 1;
      c = b + 1;

      h = e + dim;
      g = h - 1;
      ii = h + 1;
      
      p.red = (unsigned short)(((int)src[a].red + src[b].red + src[c].red
				+ src[d].red + src[e].red + src[f].red
				+ src[g].red + src[h].red + src[ii].red)/ 9);
      p.green = (unsigned short)(((int)src[a].green + src[b].green + src[c].green
				+ src[d].green + src[e].green + src[f].green
				+ src[g].green + src[h].green + src[ii].green)/ 9);
      p.blue = (unsigned short)(((int)src[a].blue + src[b].blue + src[c].blue
				+ src[d].blue + src[e].blue + src[f].blue
				+ src[g].blue + src[h].blue + src[ii].blue)/ 9);

    }
  return p;
}


/******************************************************
 * Your different versions of the smooth kernel go here
 ******************************************************/

/*
 * naive_smooth - The naive baseline version of smooth 
 */
char naive_smooth_descr[] = "naive_smooth: Naive baseline implementation";
void naive_smooth(int dim, pixel *src, pixel *dst) 
{
    int i, j;

    for (i = 0; i < dim; i++)
	for (j = 0; j < dim; j++)
	    dst[RIDX(i, j, dim)] = avg(dim, i, j, src);
}

char micro_smooth_descr[] = "micro_smooth: Removes reduntant max index bounding";
void micro_smooth(int dim, pixel *src, pixel *dst)
{
    int i, j;

    for (i = 0; i < dim; i++)
	for (j = 0; j < dim; j++)
	    dst[RIDX(i, j, dim)] = avg_micro(dim, i, j, src);
}

char unroll_smooth_descr[] = "unroll_smooth: Unrolling";
void unroll_smooth(int dim, pixel *src, pixel *dst)
{
    int i, j;

    for (i = 0; i < dim; i++)
      for (j = 0; j < dim; j++)
	  dst[RIDX(i, j, dim)] = avg_unroll(dim, i, j, src);
}

char accum_smooth_descr[] = "accum_smooth: Accumulating";
void accum_smooth(int dim, pixel *src, pixel *dst)
{
  const int area = dim * dim;
  pixel_sum tmp[area];
  int i, j;
  int idx;

  for (idx = 0; idx < area; idx++)
    initialize_pixel_sum(tmp + idx);

  for (i = 0; i < dim; i++)
    for (j = 0; j < dim; j++)
      {
	idx = RIDX(i, j, dim);
	int ii;
	int jj;

	int lastii = min(i+1, dim-1);
	int lastjj = min(j+1, dim-1);
	for(ii = max(i-1, 0); ii <= lastii; ii++) 
	  for(jj = max(j-1, 0); jj <= lastjj; jj++) 
	    accumulate_sum(tmp + RIDX(ii, jj, dim), src[idx]);
			     
      }

  for (idx = 0; idx < area; idx++)
    assign_sum_to_pixel(dst + idx, tmp[idx]);
}

char more_unroll_smooth_descr[] = "more_unroll_smooth: More unrolling";
void more_unroll_smooth(int dim, pixel *src, pixel *dst)
{
  int a, b, c, d, e, f, g, h, ii;
  int i, j;

  d = dim + 1;
  dst[0].red = COMP_CORNER_AVERAGE(RED_CORNER_SUM(0, 1, dim, d));
  dst[0].green = COMP_CORNER_AVERAGE(GREEN_CORNER_SUM(0, 1, dim, d));
  dst[0].blue = COMP_CORNER_AVERAGE(BLUE_CORNER_SUM(0, 1, dim, d));  

  for (j = 1; j < dim - 1; j++)
    {
      a = j - 1;
      c = j + 1;
      d = a + dim;
      e = j + dim;
      f = c + dim;

      dst[j].red = COMP_EDGE_AVERAGE(RED_EDGE_SUM((a),(j),(c),(d),(e),(f)));
      dst[j].green = COMP_EDGE_AVERAGE(GREEN_EDGE_SUM((a),(j),(c),(d),(e),(f)));
      dst[j].blue = COMP_EDGE_AVERAGE(BLUE_EDGE_SUM((a),(j),(c),(d),(e),(f)));
    }

  a = j - 1;
  c = a + dim;
  d = j + dim;

  dst[j].red = COMP_CORNER_AVERAGE(RED_CORNER_SUM(a, j, c, d));
  dst[j].green = COMP_CORNER_AVERAGE(GREEN_CORNER_SUM(a, j, c, d));
  dst[j].blue = COMP_CORNER_AVERAGE(BLUE_CORNER_SUM(a, j, c, d));

  for (i = 1; i < dim - 1; i++)
    {
      b = i * dim;
      a = b - dim;
      c = b + dim;
      d = a + 1;
      e = b + 1;
      f = c + 1;

      dst[b].red = COMP_EDGE_AVERAGE(RED_EDGE_SUM((a),(b),(c),(d),(e),(f)));
      dst[b].green = COMP_EDGE_AVERAGE(GREEN_EDGE_SUM((a),(b),(c),(d),(e),(f)));
      dst[b].blue = COMP_EDGE_AVERAGE(BLUE_EDGE_SUM((a),(b),(c),(d),(e),(f)));
      
      for (j = 1; j < dim - 1; j++)
	{
	  e = i * dim + j;
	  d = e - 1;
	  f = e + 1;

	  b = e - dim;
	  a = b - 1;
	  c = b + 1;

	  h = e + dim;
	  g = h - 1;
	  ii = h + 1;
      
	  dst[e].red = (unsigned short)(((int)src[a].red + src[b].red + src[c].red
				    + src[d].red + src[e].red + src[f].red
				    + src[g].red + src[h].red + src[ii].red)/ 9);
	  dst[e].green = (unsigned short)(((int)src[a].green + src[b].green + src[c].green
				      + src[d].green + src[e].green + src[f].green
				      + src[g].green + src[h].green + src[ii].green)/ 9);
	  dst[e].blue = (unsigned short)(((int)src[a].blue + src[b].blue + src[c].blue
				     + src[d].blue + src[e].blue + src[f].blue
				     + src[g].blue + src[h].blue + src[ii].blue)/ 9);
	}

      e = i * dim + j;
      d = e - dim;
      f = e + dim;
      a = d - 1;
      b = e - 1;
      c = f - 1;

      dst[e].red = COMP_EDGE_AVERAGE(RED_EDGE_SUM((a),(b),(c),(d),(e),(f)));
      dst[e].green = COMP_EDGE_AVERAGE(GREEN_EDGE_SUM((a),(b),(c),(d),(e),(f)));
      dst[e].blue = COMP_EDGE_AVERAGE(BLUE_EDGE_SUM((a),(b),(c),(d),(e),(f)));

    }

  c = i * dim;
  a = c - dim;
  b = a + 1;
  d = c + 1;

  dst[c].red = COMP_CORNER_AVERAGE(RED_CORNER_SUM(a, b, c, d));
  dst[c].green = COMP_CORNER_AVERAGE(GREEN_CORNER_SUM(a, b, c, d));
  dst[c].blue = COMP_CORNER_AVERAGE(BLUE_CORNER_SUM(a, b, c, d));

  for (j = 1; j < dim - 1; j++)
    {
      e = j + i * dim;
      d = e - 1;
      f = e + 1;
      a = d - dim;
      b = e - dim;
      c = f - dim;

      dst[e].red = COMP_EDGE_AVERAGE(RED_EDGE_SUM((a),(b),(c),(d),(e),(f)));
      dst[e].green = COMP_EDGE_AVERAGE(GREEN_EDGE_SUM((a),(b),(c),(d),(e),(f)));
      dst[e].blue = COMP_EDGE_AVERAGE(BLUE_EDGE_SUM((a),(b),(c),(d),(e),(f)));
    }

  c = j * dim + dim - 2;
  a = c - dim;
  b = a + 1;
  d = c + 1;

  dst[d].red = COMP_CORNER_AVERAGE(RED_CORNER_SUM(a, b, c, d));
  dst[d].green = COMP_CORNER_AVERAGE(GREEN_CORNER_SUM(a, b, c, d));
  dst[d].blue = COMP_CORNER_AVERAGE(BLUE_CORNER_SUM(a, b, c, d));

  /*

  for (i = 0; i < dim; i++)
    for (j = 0; j < dim; j++)
      dst[RIDX(i, j, dim)] = avg_unroll(dim, i, j, src);

  */
}


/*
 * smooth - Your current working version of smooth. 
 * IMPORTANT: This is the version you will be graded on
 */
char smooth_descr[] = "smooth: Current working version";
void smooth(int dim, pixel *src, pixel *dst) 
{
  more_unroll_smooth(dim, src, dst);
}


/********************************************************************* 
 * register_smooth_functions - Register all of your different versions
 *     of the smooth kernel with the driver by calling the
 *     add_smooth_function() for each test function.  When you run the
 *     driver program, it will test and report the performance of each
 *     registered test function.  
 *********************************************************************/

void register_smooth_functions() {
    add_smooth_function(&smooth, smooth_descr);
    add_smooth_function(&naive_smooth, naive_smooth_descr);
    add_smooth_function(&micro_smooth, micro_smooth_descr);
    add_smooth_function(&unroll_smooth, unroll_smooth_descr);
    add_smooth_function(&accum_smooth, accum_smooth_descr);
    add_smooth_function(&more_unroll_smooth, more_unroll_smooth_descr);
    /* ... Register additional test functions here */
}

